package com.company.ljh.medium;

/**
 * 695.给你一个大小为 m x n 的二进制矩阵 grid 。
 *
 * 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
 *
 * 岛屿的面积是岛上值为 1 的单元格的数目。
 *
 * 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/max-area-of-island
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 岛屿的最大面积 {
    //广度优先遍历，从一个起点开始将该岛屿全部遍历
    public int maxAreaOfIsland(int[][] grid) {
        int maxSize = 0;

        for(int i =0;i<grid.length;i++){
            for(int n=0;n<grid[0].length;n++){
                maxSize = Math.max(maxSize,getSize(grid,i,n,0));
            }
        }
        return maxSize;
    }
    private int getSize(int[][] grid,int i,int n,int size){
        if(grid[i][n] == 1){
            grid[i][n] = -1;
            size++;
        }else{
            return 0;
        }
        if(i != 0 ){
            if(grid[i-1][n] == 1)
                size = getSize(grid,i-1,n,size);
        }
        if(i != grid.length-1){
            if(grid[i+1][n] == 1)
                size = getSize(grid,i+1,n,size);
        }
        if(n != 0){
            if(grid[i][n-1] == 1)
                size = getSize(grid,i,n-1,size);
        }
        if(n != grid[0].length-1){
            if(grid[i][n+1] == 1)
                size = getSize(grid,i,n+1,size);
        }
        return size;
    }
}
